package primary.primary0;

import offer.offer02.TreeNode;

import java.util.*;

public class S0103二叉树的锯齿形层序遍历 {

    /**
     * 100
     * 要画个图看下，其实每次遍历都是先访问上一次遍历的最后一个节点的子节点，然后是先左后右还是先右后左需要一个传递值
     */
    class Solution {
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            if(root == null){
                return new ArrayList<>();
            }
            List<List<Integer>> res = new ArrayList<>();
            List<TreeNode> nodeLayer = new ArrayList<>();
            nodeLayer.add(root);
            appendRes(res, nodeLayer, true);
            return res;
        }

        private void appendRes(List<List<Integer>> res, List<TreeNode> nodeLayer, boolean direction){
            List<Integer> curLayerRes = new ArrayList<>();
            List<TreeNode> nextLayer = new ArrayList<>();
            // 空值判断会麻烦，这里直接只处理非空值
            for(int i = nodeLayer.size() - 1; i >= 0; i--){
                TreeNode curNode = nodeLayer.get(i);
                curLayerRes.add(curNode.val);
                if(direction){
                    if(curNode.left != null){
                        nextLayer.add(curNode.left);
                    }
                    if(curNode.right != null){
                        nextLayer.add(curNode.right);
                    }
                }else{
                    if(curNode.right != null){
                        nextLayer.add(curNode.right);
                    }
                    if(curNode.left != null){
                        nextLayer.add(curNode.left);
                    }
                }
            }
            res.add(curLayerRes);
            if(nextLayer.size() != 0){
                appendRes(res, nextLayer, !direction);
            }
        }
    }

    /**
     * 这个很标准，反正我就是从左到右一层层遍历树，但是我创建每一层的元素的时候，根据当前方向，要么从前insert，要么从后insert，用个双向链表
     */
    class Solution1 {
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            List<List<Integer>> ans = new LinkedList<List<Integer>>();
            if (root == null) {
                return ans;
            }

            Queue<TreeNode> nodeQueue = new ArrayDeque<TreeNode>();
            nodeQueue.offer(root);
            boolean isOrderLeft = true;

            while (!nodeQueue.isEmpty()) {
                Deque<Integer> levelList = new LinkedList<Integer>();
                int size = nodeQueue.size();
                for (int i = 0; i < size; ++i) {
                    // poll了size次，上一层清空了
                    TreeNode curNode = nodeQueue.poll();
                    // 创建每一层的元素的时候，根据当前方向，要么从前insert，要么从后insert，用个双向链表
                    if (isOrderLeft) {
                        levelList.offerLast(curNode.val);
                    } else {
                        levelList.offerFirst(curNode.val);
                    }
                    // 下一层还是从左到右
                    if (curNode.left != null) {
                        nodeQueue.offer(curNode.left);
                    }
                    if (curNode.right != null) {
                        nodeQueue.offer(curNode.right);
                    }
                }
                ans.add(new LinkedList<Integer>(levelList));
                isOrderLeft = !isOrderLeft;
            }

            return ans;
        }
    }

    /**
     * 70, 想练下deque，自己写了下
     * mark: deque只用pollFirst pollLast addFrist addLast!!!
     * 看下下面 main的测试
     */
    static class Solution3 {
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            if(root == null){
                return new ArrayList<>();
            }
            List<List<Integer>> res = new ArrayList<>();
            Deque<TreeNode> nodeRecord = new LinkedList<>();
            nodeRecord.addLast(root);
            boolean direction = true;
            while(!nodeRecord.isEmpty()){
                int curLayerSize = nodeRecord.size();
                Deque<Integer> curLayerRes = new LinkedList<>();
                for(int i = 0; i < curLayerSize; i++){
                    TreeNode curNode = nodeRecord.pollFirst();
                    if(direction){
                        curLayerRes.addLast(curNode.val);
                    }else{
                        curLayerRes.addFirst(curNode.val);
                    }
                    if(curNode.left != null){
                        nodeRecord.addLast(curNode.left);
                    }
                    if(curNode.right != null){
                        nodeRecord.addLast(curNode.right);
                    }
                }
                res.add(new ArrayList<>(curLayerRes));
                direction = !direction;
            }
            return res;
        }
    }

    public static void main(String[] args) {
        TreeNode node = new TreeNode(3);
        node.left = new TreeNode(9);
        node.right = new TreeNode(20);
        node.right.left = new TreeNode(15);
        node.right.right = new TreeNode(7);
        new Solution3().zigzagLevelOrder(node);
        // mark:注意deque的push pop，都是从最前面操作的，不是像栈一样是后面
        Deque<Integer> test = new LinkedList<>();
        test.push(1);
        test.push(2);
        test.push(3);
        test.push(4);
        System.out.println(test.pop());
        System.out.println(test.pop());
        System.out.println(test.pop());

        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());

        // 同样push，deque里面是 4 3 2 1，stack里面是 1 2 3 4
    }

}
